12.2.3 Graflar Üzerine Temel Tanımlar - 3

Komşuluk Matrisi (Adjacency Matrice):
Düğümlerden düğümlere olan bağlantıyı gösteren bir kare matrisdir; komşuluk matrisinin elemanları ki değerlerinden oluşur. Komşuluk matrisi G_dd'nin matrisel şekilde gösterilmesinden oluşur. Eğer komşuluk matrisi Gdd=[a_ij] ise, yönlü-maliyetsiz graflar için

olur; basit (yönsüz-maliyetsiz) graflar için ise,

olur.

Bitişiklik Matrisi (Incedence Matrice):
Düğümlerle kenarlar arasındaki bağlantı/bitişiklik ilişkisini gösteren bir matrisdir; matrisin satır sayısı düğüm, sütun sayısı kenar sayısına kadar olur. Bitişiklik matrisi Gdk'nin matrisel şekilde gösterilmesinden oluşur. Eğer bitişiklik matrisi Gdk=[m_ij] ise, maliyetsiz graflar için,

olur.

Düğüm Derecesi (Node Degree): Düğüme bağlı toplam uç sayısıdır; çevrimli kenarlar aynı düğüme hem çıkış hem de giriş yaptığı için dereceyi iki arttırır. Yönlü graflarda, düğüm derecesi giriş derecesi (input degree) ve çıkış derecesi (output degree) olarak ayrı ayrı belirtilir.